#!
sub LCS
{
    $X=shift;
    $Y=shift;

    @S1 = split //,$X;
    @S2 = split //,$Y;
    
    $m = @S1;
    $n = @S2;

    for $i (1..$m)
    {
        $$c[$i][0] =0 ;
    }
    for $j (1..$n)
    {
        $$c[0][$j] =0;
    }
    
    for $i (1..$m)
    {
        for $j (1..$n)
        {
            if($S1[$i-1] eq $S2[$j-1])
            {
                $$c[$i][$j] = $$c[$i-1][$j-1] + 1;
#            $b[$i][$j] = "slant";
            }
            elsif ($$c[$i-1][$j] > $$c[$i][$j-1])
            {
                $$c[$i][$j] = $$c[$i-1][$j];
#           $b[$i][$j] = "up";
            }
            else
            {
                $$c[$i][$j] = $$c[$i][$j-1];
#            $b[$i][$j] = "left";
            }
        }
    }
    return $$c[$m][$n];
}


print LCS ("ABC","BAC");

